\section{Предлагаемое решение} %(основная часть)}

\subsection{Построение графа де Брюина}
Из-за сопряженной структуры ДНК, каждый парный рид корректнее представлять себе как два сопряженных парных рида. Для того чтобы учесть эту специфику, явно добавим сопряженные парные риды к множеству входных пар.

Построение несжатого графа де Брюина достаточно прямолинейно. 

Заранее выберем \textbf{четную} константу $k$, она останется неизменной до самого конца. 

Проходом по всем ридам, извлекаем все $k$-меры, присутствующие в каждом из них и складываем их в эффективную по структуру хранения. 

Для каждого $k-1$-мера (вершины) и $k$-мера (ребра) в графе найдется сопряженный. Это в частности означает, что для каждого пути в графе найдется сопряженный ему путь.

\textbf{Замечание:} Так как выбранное $k$ является четным, то никакой $(k-1)$-мер не может оказаться самосопряженным.
Это означает, что все вершины разбиваются на сопряженные пары. При этом самосопряженные ребра могут присутствовать в графе. Ясно, что ребро является самосопряженным т. и т.т., когда оно соединяет пару сопряженных вершин.

\subsection{Построение сжатого графа}
\textit{Простым} будем называть путь в графе, входящая и исходящая степень всех внутренние вершин которого равны $1$.

Операцию замены простого пути ребром, содержащим последовательность ранее соответствовавшую этому пути, будем называть \textit{конкатенацией} ребер этого пути.

\textbf{Замечание.} Так как в качестве длины ребра $e$ мы рассматриваем количество $k$-меров, принадлежащих ему, то она оказывается аддитивна относительно операции конкатенации. $e =  concat(p_1,p_2,\dots, p_n) \Rightarrow length(e) = \sum_{i=1}^n{length(p_i)}$

Помимо самого графа, нам будет необходим \textit{индекс} $k$-меров в этом графе. Это структура, позволяющая для каждого $k$-мера получить идентификатор ребра, в котором находится данный $k$-мер и его позицию относительно начала ребра (количество нуклеотидов, которые нужно пропустить, чтобы его считать).

При условии, что последовательности нуклеотидов хранятся в простых линейных структурах (например, массивах), строить сжатый граф напрямую по псевдокоду алгоритма может оказаться крайне неэффективно. Действительно, ведь если объединение двух последовательностей происходит за время $O($их длины$)$, то построение длинного ребра сжатого графа может занять квадратичное от его длины время.

Предположим, что у нас имеется несжатый граф, тогда по следующему алгоритму можно эффективно построить сжатый граф вместе с заполнением индекса.

\begin{algorithm}[H]
\label{alg_cond}
\caption{Алгоритм сжатия графа}
\textbf{Вход:} . $D_k$ --- граф де Брюина\\
\textbf{Выход:} $C_k$ --- сжатый граф де Брюина, $I$ --- индекс по $k$-мерам. \\
\begin{algorithmic}
\FOR{$s$ --- $k$-мер, присутствующий в $D_k$}
\IF{$s$ отсутствует в индексе}
\STATE Пройти от него влево по несжатому графу пока не встретим развилку (вершину у которой входящая или исходящая степень $>1$) или тупик (вершину исходящей степени $0$)
\STATE От найденной позиции пройти направо до ближайшей развилки или тупика, считывая пройденные ребра в последовательность нуклеотидов.
\STATE Найти (с помощью индекса) в уже поенной части $C_k$, соответствующие началу и концу последовательности, по необходимости создав их.
\STATE Добавить в $C_k$ ребро между этими вершинами, соответствующее последовательности и внести позиции соответствующих $k$-меров в $I$.
\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}

\subsection{Графовые операции}
Определим операции преобразования графа, которые наиболее естественным образом позволят нам выразить алгоритмы упрощения графа. 

Их условно можно разделить на операции низкого и высокого уровней.

К операциям низкого уровня относятся операции добавления/удаления ребра/вершины. 

При каждом добавлении/удалении ребра необходимо преобразование индекса.

Операции высокого уровня это:
\begin{itemize}
\item \textit{Конкатенация} ребер простого пути. \emph{concat(P)} \

Описывалась ранее.\
Можно было ввести конкатенация двух ребер и выразить рассматриваемую операцию через нее, но в некоторых случаях, реализация последней может оказаться существенно эффективнее, так как сжатие длинного пути $P$ по парам ребер может занять $O(length(P)^2)$ времени ($length(P)$ ---суммарная длина всех ребер, входящих в путь).%уже сталкивались с этим при сжатии графа (не только конкатенация последовательностей, но и индексы и т.п.) 

\item \textit{Разделение} ребра $e$ в заданном отношении $\alpha$. \emph{} \
Ребро $e$ удаляется из графа. Появляются ребра $e_1, e_2: e=concat(e_1, e_2) \& l_{e_1} / l_{e_2} = \alpha$ и вершина их соединяющая.


\item \textit{Проекция} ребра $e_1$ на ребро $e_2$. \
Семантика данной операции заключается в переносе всей информации с ребра $e_1$ на ребро $e_2$. Ребро $e_1$ удаляется из графа. Если при этом появляется висячая вершина, то она также удаляется из графа.%может, все-таки сказать про то, что начала должны совпадать

\end{itemize}

Операции высокого уровня реализованы через операции низкого уровня.

\subsection{Сжатый граф, учитывающий сопряженность} %Condensed \dbg that we work with (implicit reverse complement info consistensy maintaining)}

По аналогии с несжатым графом, в сжатом графе, после его построения, каждому элементу соответствует сопряженный. %Каждому пути, в том числе простому, в исходном графе соответствует сопряженный такого же вида, следовательно каждому ребру сжатого графа будет соответствовать сопряженное ребро (с сопряженной последовательностью), а каждой вершине --- сопряженная вершина.

Это естественное ограничение (свойство) пришло из сопряженной структуры ДНК (и соответствующей обработки входных данных).
Но мы собираемся преобразовывать граф, при этом это ограничение, вообще говоря может оказаться нарушенным.

\textbf{Замечание:} сопряженные вершины сжатого графа могут быть соединены как одним самосопряженным, так и двумя сопряженными (но не самосопряженными) ребрами.
%для каждого $k$-мера (ребра) в графе найдется сопряженный (аналогично и для $k-1$-мера (вершины)). Это в частности означает, что для каждого пути в графе найдется сопряженный ему путь.

Некоторые ассемблеры явно не поддерживают согласованность сопряженных путей при выполнении преобразований графа, надеясь на то, что все преобразования пройдут симметрично для участков графа, соответствующих разным стрендам. Но если надежда не оправдывается (а это запросто может произойти, так как зачастую одни и те же последовательности присутствуют на обоих стрендах), то полученный граф окажется в противоречивом состоянии, что может привести к ошибкам в итоговой сборке. %в последствии придется разрешать непростые конфликты, а обычно этого не делают. 

Мы будем использовать структуру сжатого графа, явно учитывающую сопряженность.

Можно представлять себе, что в графе все вершины и ребра ``сдвоенные''. Верхняя и нижняя половины вершин соответствуют сопряженным $(k-1)$ мерам (самосопряженных $(k-1)$-меров у нас не бывает из-за четности $k$). Если $e:v_1\rightarrow v_2$, то $e':v'_2\rightarrow v'_1$. 

Вершину, сопряженную к вершине $v$ будем обозначать $conj(v)$ (от англ. conjugate). Аналогично и для ребер.

Будем считать, что у нас есть способ эффективно переходить с элемента графа на его сопряженный и реализуем все операции, предоставляемые графом таким образом, чтобы они сразу же влияли бы и на сопряженные элементы.

При добавлении/удалении вершины/ребра, будем сразу добавлять/удалять из графа сопряженный элемент. Единственная тонкость заключается в обработке самосопряженных ребер. При добавлении их нужно добавлять в единственном экземпляре, а при удалении не пытаться удалить их дважды.

За счет такой модификации операция разделения ребра автоматически начинает корректно обрабатывать сопряженные элементы.

Операция проекции также будет работать корректно, с тем лишь естественным ограничением, что запрещается проецировать ребро на сопряженное.

В общем случае, при конкатенации простого пути ребер, будет автоматически корректно сжиматься и комплементарный путь. 

Единственная опасность заключается в следующем: если последняя вершина $v_{last}$ в пути является сопряженной некоторой его внутренней вершине $v$ ($conj(v) = v_{last}$), то действуя по общей схеме, мы бы добавили ребро между $v_{first}$ и $v_{last}$, а затем, удалив $v$, удалили бы и $v_{last}$ вместе с только что добавленным ребром. Если рассмотреть ситуацию подробнее, то можно доказать , что она возможна только когда рассматриваемый простой путь содержит самосопряженное ребро.

Итак, случай присутствия в пути самосопряженного ребра, является особым. Пусть $P = \{e_i\}_{i=1}^{n}$, $e_k$ --- самосопряженное, и $k>n/2$ (случай $k<n/2$ разбирается аналогично). Ясно, что для $i=1 \dots k-1$ $conj(e_{k-i})=e_{k+i}$. Нужно дополнить путь недостающими сопряженными ребрами, после чего обработать его как обычно (добавить в граф новое самосопряженное ребро $e=concat(e_1, \dots e_{k-1}, e_k, conj(e_{k-1}), \dots , conj(e_{1}))$, удалить из графа все внутренние вершины пути вместе с инцидентными им ребрами (при этом удалятся и их сопряженные).

\subsection{Дополнительная информация}
Помимо самих последовательностей, с ребрами полезно ассоциировать еще несколько видов информации: уже упоминавшуюся информацию о среднем покрытии ребра и информацию о межреберных расстояниях (см. далее). Различные ассемблеры используют различные политики работы с этими видами информации. Одна из проблем заключается в том, что чтобы их вычислить, нужно знать какому участку графа соответствует каждый из исходных ридов (процесс выяснения этих участков называется \textit{прикладыванием} ридов). Но в процессе преобразований из графа исчезают ребра и многие риды перестают точно прикладываться к графу. Таким образом, прикладывание ридов к преобразованному графу может оказаться непростой задачей, а информация, полученная в ходе этого процесса может оказаться не полной. 

В данной работе предлагается следующая стратегия для работы с любым типом дополнительной информации. 
\begin{itemize}
\item первоначальный подсчет на графе до преобразований
\item изменение информации при преобразованиях графа в соответствии с семантикой операций, описанных ранее
\end{itemize}

\textbf{Замечание.} Преобразование дополнительной информации, соответствующей сопряженным элементам, нужно производить одновременно и симметрично, для сохранения ее непротиворечивости.  Везде далее считается, что так и происходит (о том как это реализовано см. раздел \ref{handlers}).
 
Преимущества такого подхода:
\begin{itemize}
\item прикладывание ридов осуществляется очевидным образом с помощью индекса $k$-меров
\item практически не происходит потери информации в процессе преобразований
\item появляется возможность использовать дополнительную информацию в процессе преобразований графа для разрешения спорных ситуаций
\end{itemize}

\subsection{Покрытие}
Информация о среднем покрытии нужна будет нам в первую очередь для удаления из графа ошибочных ребер. Также она важна для определения приблизительной кратности контигов при скэффолдинге.

\subsubsection{Первоначальный подсчет}
Обычно под покрытием некоторого участка генома подразумевают среднее по всем нуклеотидам количество ридов, покрывающих этот нуклеотид.

Для нас будет удобно немного модифицированное понятие покрытия: мы будем рассматривать среднее покрытие $k$-меров ребра, то есть среднее по всем $k$-мерам количество ридов, покрывающих этот $k$-мер ($coverage(e)$).

Модель подсчета такова: разбить рид на множество $k$-меров, учесть каждый из них в покрытии соответствующего ребра.

Непосредственно подсчет происходит путем прикладывания одиночных ридов к сжатому графу. 

Для каждого ребра $e$, по которому прошел рид $r$, увеличим его покрытие на количество $k$-меров в перекрытии $r$ и $e$, в конце добавляем нормировку на $1/length(e)$.

\textbf{Замечание:} так как множество ридов было дополнено сопряженными, то покрытие сопряженных ребер автоматически окажется одинаковым.

\subsubsection{Правила преобразования}
При конкатенации простого пути покрытие нового ребра получается как взвешенная сумма покрытий склеиваемых ребер. Если $e=concat(e_1,e_2)$, то $coverage(e) = (coverage(e_1)*length(e_1) + coverage(e_2)*length(e_2))/length(concat(e_1,e_2))$.

При разделении ребра, покрытия обоих итоговых ребер будем считать равными исходному покрытию (здесь происходит потеря некоторой информации).

При проекции ребра $e_1$ на $e_2$, покрытие $e_2$ увеличивается на покрытие $e_1$.

\subsection{Информация о межреберных расстояниях}
Как уже отмечалось, информация, извлекаемая из факта парности ридов, необходима для качественной сборки. Она активно используется как при разрешении повторов, так и на этапе скэффолдинга.

Но с получением информации есть одна проблема: на самом деле, единичный парный рид не дает нам представления об истинном расстоянии между его концами. Когда говорят, что дано множество парных ридов с внутренним расстоянием $l$, предполагается, что $l$ --- матожидание истинного распределения внутренних расстояний (см. рис. \ref{ris:real_insert})

\begin{figure}[h]
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=0.9\linewidth]{new_paired_dist_1} \\ а)}
\end{minipage}
\hfill
\begin{minipage}[h]{0.49\linewidth}
\center{\includegraphics[width=0.9\linewidth]{new_paired_dist_2} \\ б)}
\end{minipage}
\caption{
%получена прикладыванием ридов
(а) Гистограмма реальных внутренних расстояний парных ридов для данных по P. syringae от платформы Illumina из \cite{DMS10}. Похожа на смесь двух распределений: распределения  около предположительного внутреннего расстояния библиотеки и ``широкого'' фона. (б) Участок той же гистограммы около пика. Распределение, соответствующее (б) имеет большое стандартное отклонение, порядка 20\% от среднего значения.
}
\label{ris:real_insert}
\end{figure}

Чтобы преодолеть эту проблему, целесообразно ``перенести'' информацию о парных ридах на ребра сжатого графа и пересчитать ее как расстояние между началами соответствующих ребер. Ребра сжатого графа, являются в среднем достаточно длинными, и анализ информации по всем прошедшим по ним ридам может дать хорошее приближение приближение истинных расстояний. 

Итак, информация о парных ридах трансформируется в еще один тип важной дополнительной информации, ассоциированной с графом --- информацию о предположительных расстояниях между некоторыми парами ребер в итоговой сборке.

Мы будем представлять ее в виде некоторой структуры, хранящей отображение из некоторого множества троек $(a,b,d')$, где $a,b$---ребра, $d'$ --- возможно отрицательное, предположительное расстояние между их началами, в значение некоторого условного веса истинности этой информации. При этом, вместе с тройкой $(a,b,d')$, там также содержится и тройка $(b,a,-d')$ с тем же весом. Эти записи добавляются и удаляются из структуры парами. За счет такого представления информации, нам достаточно рассматривать только тройки, начинающиеся с $e$, чтобы получить полную информацию о ее парных ребрах.

Так как мы заботимся о непротиворечивости сопряженной информации, то в структуре также должны содержаться и соответствующие записи о сопряженных парах ребер (это свойство будет достигнуто автоматически, за счет симметричности производимых для сопряженных элементов операций).

\subsubsection{Первоначальный подсчет}
В чем измерять веса? На первый взгляд, самым естественным вариантом весовой функции истинности некоторого расстояния, является количество парных ридов, согласованных с этим расстоянием. К сожалению, способ корректного поддержания такой весовой функции при преобразованиях, нетривиален. 

Предлагается следующая модель подсчета: в начале из каждого парного рида, по одной из двух возможных стратегий, извлекается множество пар $k$-меров, после чего информация о расстоянии с каждой пары переносится на соответствующие ребра с весом 1 (весовая функция --- количество пар $k$-меров, поддерживающих некоторое расстояние).

Считаем, что риды имеют внутреннее расстояние $d$.
Стратегии получения множества пар $k$-меров из парного рида.
\begin{itemize}
\item ``Скользящие'' пары $k$-меров на расстоянии $d$. Минус в том, что если раньше была информация об участках генома на расстоянии $d+l$, то осталась --- на $d+k$. (сможем разрешить меньше повторов) 
\item Все возможные пары $k$-меров на соответствующих расстояниях.
\end{itemize}

Если пара $k$-меров $(a|b)$ на расстоянии $d'$ находятся в ребрах $e_a$ и $e_b$, начиная с позиций $p_a$ и $p_b$ соответственно, то эта пара приносит информацию о том, что $e_a$ и $e_b$ находятся на расстоянии $d'+p_b-p_a$ с весом $1$.

Непосредственно подсчет происходит путем прикладывания парных ридов к сжатому графу. При этом в случае обеих стратегий нет необходимости явно учитывать по-отдельности каждую извлеченную пару $k$-меров, так как количество пар, дающих вклад в расстояние между парами ребер и сами расстояния могут быть явно вычислены исходя из длин ребер и степеней их пересечений с ридами.

\subsubsection{Правила преобразования}
При конкатенации ребер простого пути $\{e_i\}$ в ребро $e$, нужно преобразовать всю информацию, ранее затрагивавшую хотя бы одно из ребер $e_i$ в корректную информацию, включающую новое ребро. 

Не будем описывать процесс формально, а приведем поясняющий пример. Допустим, ранее в структуре находилась информация $(e_2, e_a, d')$ с весом $w$. Теперь она (вместе с информацией $(e_a, e_2, -d')$) должна исчезнуть из структуры, а информация $(e, e_a, d' - length(e_1))$ добавиться в структуру с весом $w$.

Весовые функции специально выбирались так, чтобы обладать свойством аддитивности относительно конкатенации.

Интересно, если немного задуматься, то станет ясно, что самая простая стратегия, которая, рассматривая ребра пути одно за другим ``переносит'' парную информацию с него на ребро $e$ , корректно обрабатывает практически все нетривиальные случаи: присутствие информации вида $(e_i, e_j,.)$ или $(e_i, conj(e_j),.)$

Отдельно нужно рассмотреть лишь случай наличия информации вида $(e_i,e_i,.)$.

При разделении ребра $e$ на $e_1,e_2$ в отношении $\alpha$, информация разделяется между ребрами в отношении $\alpha$. То есть, вместо информации $(e, e_a, d)$ с весом $w$, добавляется $(e_1, e_a, d)$ с весом $\alpha * w$ и $(e_2, e_a, d - length(e_1))$ с весом $(1-\alpha) * w$. Как и в случае с покрытием, здесь, естественно, происходит некоторая потеря информации.

При проекции ребра $e_1$ на ребро $e_2$, вся парная информация ребра $e_1$ без изменений добавляется к $e_2$

\subsubsection{Кластеризация ``на лету''}
Как уже отмечалось ранее, из-за значительного разброса истинных внутренних расстояний, чтобы получить представление об истинном расстоянии между двумя ребрами, необходима интеллектуальная обработка имеющихся данных. Задача достаточно непростая и не решается банальным усреднением всех значений с учетом весов. Во-первых, не известно сколько различных расстояний нужно получить, ведь два ребра могут встречаться в правильной сборке несколько раз на различных расстояниях. Это приводит к необходимости выделения кластеров среди имеющихся расстояний и поиску наиболее вероятного расстояния внутри каждого кластера в отдельности. Во-вторых, не трудно представить себе ситуацию, в которой, при условии безошибочных расстояний, два ребра вообще не могли быть связаны парными ридами. В этом случае внутренние расстояния всех парных риды, которые связывают эти ребра отличаются от предполагаемых, что может привести нас к совершенно неправильной оценке расстояний между этими ребрами. Таким образом, проблема оценки истинных расстояний между ребрами является сложной задачей, дальнейшее обсуждение которой выходит за рамки данной работы.

Но есть момент, который мы не можем обойти стороной: все из-за того же разброса внутреннего расстояния, для сохранения всей парной информации ``в лоб'' потребовалось бы много места. Чтобы сэкономить память, предлагается применить простую стратегию кластеризации. Выберем константу $\epsilon$. При добавлении в структуру информации о тройке $(e_a,e_b,d_{a,b})$ с весом $w$, проверяем не находится ли в ней информация о $(e_a,e_b,d'_{a,b})$, где $|d-d'|<\epsilon$ расстоянии и, если такая была, добавляем новую информацию к уже имевшейся, корректируя значение расстояния и вес. Новое расстояние определяется как взвешенное среднее исходных расстояний, а вес --- их суммарному весу. 

\subsection{Алгоритмы коррекции графа}

Были разработаны собственные методы обнаружения и устранения ошибочных участков графа, которые несмотря на свою внешнюю простоту, на практике работают не хуже, чем сложные алгоритмы, используемые в Velvet, SOAP \textit{de novo} или Euler-SR (речь про их алгоритмы удаления пузырей).

За счет постоянного хранения и поддержания информации о межреберных расстояниях, она может использоваться как один из факторов для определения является ли ребро ошибочным, с целью повышения точности алгоритмов.

При этом, разработанные алгоритмы показывают хорошие результаты даже если вовсе запретить им использовать последовательности нуклеотидов (возможность работы в условиях ``бесконтекстного'' подхода было одним из требований, предъявлявшихся к новым алгоритмам).
 
\textbf{Замечание 1:} приведенные ниже алгоритмы запускаются один за другим в несколько итераций, так в результате работы каждого из них могут образоваться новые элементы, за удаление которых отвечают остальные. Также как и в Velvet, устранение ошибочных соединений запускается после удаления тупиков и пузырей, чтобы дать возможность правильным, но коротким и плохо покрытым ребрам ``слиться'' с более хорошо покрытыми соседями.

\textbf{Замечание 2:} практически для всех констант, фигурирующих ниже есть значения по умолчанию, определяемые с учетом конкретных характеристик графа.

\subsubsection{Удаление тупиков}
Как нетрудно видеть, в зависимости от того, в начале или в конце рида случилась ошибка, тупики бывают двух типов: ``входящие''  в граф и ``выходящие'' из него соответственно. Также ясно, что сопряженным участком каждому ``входящему'' тупику будет ``выходящий'' тупик и наоборот. Таким образом, можно искать и удалять, скажем, только ``выходящие'' тупики (ведь вместе с каждым элементом из графа удаляется его сопряженный).

\begin{algorithm}[H]
\label{alg_tip_clip}
\caption{Алгоритм удаления ``тупиков''}
\textbf{Вход:} . $C_k$ --- сжатый граф де Брюина, $l_{max}$ --- максимальная длина ``тупика''\\
\textbf{Выход:} $C'_k$ --- сжатый граф де Брюина, не содержащий ``тупиков'' \\
\begin{algorithmic}
\FOR{$e$ --- ребро графа $C_k$, не имеющее продолжения, и $length(e)<l_{max}$}
\IF{Есть альтернативное ребро $e'$, такое что $start(e) = start(e')$
 (из всех таких ребер выбирается наиболее покрытое ребро)}
\IF{Выполняются некоторые условия на $e, e'$ (о них дальше)}
\STATE Удаляем $e$ из графа
\STATE Пытаемся сжать окрестность его начала и включаем новое ребро (если появилось) в обход (так как новое ребро вполне может оказаться тупиком)
\ENDIF
\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}

\textbf{Замечание: } чтобы в процессе работы было удалено как можно меньше нуклеотидов, ребра необходимо перебирать в порядке возрастания их длин. Чтобы добиться того же эффекта, к примеру, ассемблеру ABySS приходится производить удаление тупиков в несколько итераций, каждый раз увеличивая пороговое значение для длины рассматриваемых тупиков.

Опишем условия на $e,e'$, при которых ребро $e$ \textbf{не будет} удалено:
\begin{itemize}
\item $coverage(e) > max\_cov$, где $max\_cov$ --- константа, задаваемая пользователем
\item $coverage(e) > r * coverage(e')$, где $r$ --- константа, задаваемая пользователем
\item множества парных к $e$, $e'$ ребер не имеют пересечения
\end{itemize}

Первые два условия похожи на те, которые использует Velvet, но он не дает возможности задания конкретных констант вручную.

Третье условие реализовано, но является опциональным.

\subsubsection{Удаление пузырей}
\textit{Простым} назовем пузырь, состоящий из одного ребра.
Заметим, что последовательным удалением простых пузырей и сжатием однозначных участков, можно удалить достаточно сложные структуры ``наползающих'' друг на друга пузырей.

\begin{algorithm}[H]
\label{alg_bulge_rem}
\caption{Алгоритм удаления ``пузырей''}
\textbf{Вход:} . $C_k$ --- сжатый граф де Брюина, $l_{max}$ --- максимальная длина ``пузыря'', $\delta$ --- максимальная разница длин между ребром и альтернативным путем\\
\textbf{Выход:} $C'_k$ --- сжатый граф де Брюина, не содержащий ``пузырей'' \\
\begin{algorithmic}
\FOR{$e$ --- ребро графа $C_k$ и $length(e)<l_max$}
\IF{Есть альтернативный путь $P: start(P)= start(e) \wedge end(P) = end(e)$, такой что $|length(P) - length(e)| < \delta$ (из всех путей, удовлетворяющих этому условию выбирается наиболее покрытый в среднем)}
\IF{Выполняются некоторые условия на $e, P$ (о них дальше)}
\STATE Разбиваем $e$ на ребра, длины которых пропорциональны длинам ребер в $P$
\STATE Одно за другим, проецируем новые ребра на соответствующие ребра $P$ (используя описанную ранее соответствующую операцию графа)
\STATE Пытаемся сжать окрестности концов $e$ и включаем новые ребра (если появились) в обход, так как они могут оказаться новыми простыми пузырями.
\ENDIF
\ENDIF
\ENDFOR
\end{algorithmic}
\end{algorithm}

Опишем условия на $e,P$, при которых ребро $e$ \textbf{не будет} удалено:
\begin{itemize}
\item $coverage(e) > max\_cov$, где $max\_cov$ --- константа, задаваемая пользователем
\item $coverage(e) > r * coverage(P)$, где $r$ --- константа, задаваемая пользователем, а $coverage(P)$ -- среднее покрытие пути $P$
\item последовательности нуклеотидов ребра $e$ и пути $P$ имеют редакционное расстояние > $max_red$, где $max\_red$ --- константа, задаваемая пользователем
\item множества ребер, парных к $e$ и ребрам из $P$ не имеют пересечения
\end{itemize}

Как и в случае с удалением тупиков, первые три условия похожи на те, которые использует Velvet, но он не дает возможности конфигурации конкретных констант вручную.

Здесь третье и четвертое условия являются опциональными.

\textbf{Замечание. } Есть еще одно условие, при котором ребро $e$ не будет удалено: оно не будет удалено, если $P$ содержит $conj(e)$ или $P$ содержит $e_i$ и $e_j$, такие что $e_i=e_j$ или $e_i=conj(e_j)$. Наличие этого условия на структуру пути $P$ обусловлено с одной стороны нашей стратегией поддержания корректного состояния сопряженных элементов, а с другой --- нежеланием возиться с большим количеством хитрых случаев, которые разбирает Velvet при ``склеивании'' параллельных путей.

\subsubsection{Удаление ошибочных соединений}
Удаление ошибочных соединений происходит так же, как и у всех. Ошибочными будем признавать все ребра $e$:
\begin{itemize}
\item $length(e)<l_{max}$
\item $coverage(e) < max\_cov$
\end{itemize}
, где $l_{max}$ и $max\_cov$ --- задаваемые пользователем константы

Будем удалять из графа все такие ребра. Как и раньше, удаление одного ошибочного соединения может привести к образованию новых ошибочных соединений, которые будут включены в обход и тут же удалены.